package 排序算法.计数排序;

import java.util.Arrays;

/**
 * 计数排序
 * 时间复杂度：O(n + m)
 * 空间复杂度：O(n + m)
 * 稳定
 */
public class CountSort {
    public static void main(String[] args) {
        int[] arr= {8,9,58,5,6,3,5,87,0,5,5};
        countSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    private static void countSort(int[] arr) {
        //获取数组中的最大值和最小的值
        int maxNum = findMax(arr);
        int minNum = findMin(arr);
        //创建一个数组长度可以容纳原始数组中的最小值到最大值之间的所有的数字，用于记录原始数组中每个数字出现的次数
        //公式：index(新建的角标) = num(原始数组中的数字) - minNum(原始数组中的最小值)
        //根据新建数组中下标有序并递增的规则来对原始数组进行排序
        int[] temp = new int[maxNum - minNum + 1];
        for (int i = 0; i < arr.length; i++) {
            //遍历元素数组，统计该数字在新数组的对应的下标中出现的次数
            temp[arr[i] - minNum]++;
        }

        int i = 0;

        for (int index = 0; index < temp.length; index++) {
            //遍历新建的数组，判断每个下标的只要不为0就遍历该值，通过公式计算出该下标对应的数字并将其放到原始数组中，最后对该次数--,进而派序
            while (temp[index] != 0){
                arr[i++] = index + minNum;
                temp[index]--;
            }
        }
    }

    private static int findMin(int[] arr) {
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min){
                min = arr[i];
            }
        }
        return min;
    }

    private static int findMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }
        return max;
    }
}
